In existing radio communication protocols, including broadcast and unicast protocols, data to be transmitted is segmented into data portions defining the payload of protocol data units. The protocol data units are, e.g., frames generated by a data link layer. The data portions are transmitted from a transmitter to one or more receivers, e.g., remote nodes of a radio network. Broadcast examples include Digital Video Broadcasting (DVB) and Bluetooth broadcasting. A unicast example in cellular telecommunications for the segmentation includes the Radio Link Control (RLC) layer of the Third Generation Partnership Project (3GPP) Long Term Evolution (LTE).
If the radio communication protocol supports positive or negative acknowledgements, each receiver can report which data portions have not been successfully received, or alternatively, which data portions have been successfully received. The missing data portions are retransmitted. However, retransmitting individual receiver-specific data portions from the transmitter to the corresponding receivers is complicated to handle, causes latency and is inefficient in terms of power consumption at both the transmitter and the receiver and in terms of radio resources, including the time needed for transmitting the data, reporting acknowledgements and retransmitting data portions.
If the radio communication protocol does not support acknowledgements, the transmitter may preemptively retransmit certain data portions in order to increase the probability of the complete data been correctly received. However, preemptively retransmitting certain data portions without knowing if and which data portions are missing at the receivers is even more inefficient in terms of radio resources.
The document “An Improved Broadcast Retransmission Protocol” by J. J. Metzner, IEEE Transactions on Communications, Vol. COM-32, No. 6, pp. 679-683, describes a broadcast protocol for transferring one file as the data to multiple different sites. The data for transmission is segmented into N frames yn, n=1, . . . , N, each consisting of B bits. Thus, a frame can be considered as an element in the Galois field GF(2B). The retransmitted frames are not exact replicas of initially unacknowledged frames, but are chosen to provide additional information to all sites having one or more non-decodable frames. The frames are encoded by means of a Reed-Solomon code and the resulting code symbols become the frames for transmission or retransmission. Once a receiver has decoded correctly any N frames out of the total of N+K transmitted frames, the receiver can recover the entire data yn, n=1, . . . , N, because Reed-Solomon codes are maximum distance separable (MDS).
Low-density parity-check (LDPC) codes are another example of linear block codes for erasure channels. LDPC codes can approach the theoretical capacity of the channel. Moreover, fountain codes (also referred to as rateless erasure codes) have been constructed to provide a large number of N+K frames (e.g., approaching infinity), while the receiver needs to collect N′=(1+ϵ)·N frames to decode the data. Examples of fountain codes include raptor codes. In practice, it is desirable that the probability for decoding is as high as possible for small ϵ. For good fountain codes, ϵ approaches zero as N+K approaches infinity. That is, the fountain code is asymptotically optimal. J. D. Ellis; M. B. Pursley, “Adaptive Transmission Protocols for Fountain-Coded Multicast Transmissions in Packet Radio Networks,” in IEEE Transactions on Communications, vol. PP, no. 99, pp. 1-1, describe applications of Fountain coding.
While the retransmission protocols based on Reed-Solomon codes or more modern codes such as raptor codes have been proven to work well, existing schemes based on Reed-Solomon codes may suffer from problems of algorithmic complexity, especially when the size, 2B, of the field becomes large. For example, the arithmetic in GF(2512) is challenging and not-well suited for implementation in low-end devices. More recent methods based on LDPC codes or raptor codes require iterative decoders and the systemization complexity is not negligible. In this respect, systemization may refer to any process of arranging all the components (e.g., in software and hardware) needed to implement a certain technique (e.g., an encoding process and/or a decoding process). More specifically, systemization may encompass arranging and/or configuring at least one of memory, digital signal processors, hardware buses and algorithms for implementing a certain technique.
In summary, existing retransmission protocols can suffer from high algorithmic complexity or complex systemization, or can be not well-suited for applications targeting low-end devices, such as mesh networks including Internet of Things (IoT) devices having a limited power and processing capacity.